package junior.回溯法;

/**
 * N种物品中选取若干件（同一种物品可多次选取）放在空间为 Capacity 的背包里
 * 每种物品的体积为C1，C2，…，Cn，与之相对应的价值为W1,W2，…，Wn，怎么样选择放入背包的物品以使得背包的总价值最大？
 */
public class 完全背包 {
    static int N = 5; //商品数量
    static int Capacity = 20; //背包容量
    //      初始化数据(注意适配边界)
    static int[] weight = {2  ,3  ,4  ,5  ,9};  // 商品重量
    static int[]  price = {3,  4,  5,  8,  10};  // 商品价格
    static int[] stack = new int[100000]; // 构造解空间
    static int[] result = new int[10000]; // 保存结果
    static int top = 0, total=0, maxPrice = 0, tempPrice = 0, tempWeight=0;

    public static void main(String[] args) {
        fun(0);
        System.out.println("解空间个数: " + total);
        System.out.println("最大价值: " + maxPrice);
        showResult(result);
    }
    public static void fun(int n){
        if(n == N){
            for (int i = 0; i < top; i++) {
                if(stack[i] == 0)
                    continue;
                tempPrice += price[stack[i]-1];
                tempWeight += weight[stack[i]-1];
            }
            if(tempWeight <= Capacity && maxPrice <= tempPrice) {
                maxPrice = tempPrice;
                for (int i = 0; i < top; i++) {
                    if(stack[i] == 0)
                        result[i] = stack[i];
                    else
                        result[i] = stack[i]-1;
                }
            }
            tempPrice = 0;
            tempWeight = 0;
            total++;
            return;
        }
        for (int i = 0; i <= 5; i++) {
            stack[top++] = i;
            fun(n+1);
            top--;
        }
    }
    public static void showResult(int[] result){
        System.out.println();
        System.out.println("全部的商品为:");
        System.out.print("商品重量: ");
        for (int i = 0; i < N; i++) {
            System.out.print(weight[i]+"\t");
        }
        System.out.println();
        System.out.print("商品价格: ");
        for (int i = 0; i < N; i++) {
            System.out.print(price[i]+"\t");
        }
        System.out.println();
        System.out.print("商品编号: ");
        for (int i = 0; i < N; i++) {
            System.out.print(i+"\t");
        }
        System.out.println();
        System.out.println();
        System.out.println("装入的商品为:");
        for (int i = 0; i < N; i++) {
            if(result[i] != 0)
            System.out.println("商品编号: "+(result[i])+"\t\t商品重量: "+weight[result[i]]+"\t\t商品价格: "+price[result[i]]);

        }
    }
}
